package 中缀转后缀;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

import 逆波兰计算器_后缀.逆波兰计算器_后缀;


public class 中缀转后缀 {
	public static void main(String[] args) {
		//直接使用String类型的中缀表达式不方便，转成List
		String exp = "1 + ( ( 2 + 3 ) * 4 ) - 5";
		String[] split = exp.split(" ");
		List<String> list = Arrays.asList(split);
		
		//调用方法转成后缀表达式
		List<String> suffixExp = convSuffixExp(list);
		System.out.println(list);
		System.out.println(suffixExp);
		
		逆波兰计算器_后缀 cal = new 逆波兰计算器_后缀();
		System.out.println(cal.cal(suffixExp));  //16
	}

	private static List<String> convSuffixExp(List<String> list) {
		//定义两个栈，一个存放符号，一个存放中间运算结果和符号，
		//由于数栈只有入栈没有出栈，还要逆序，所以用List代替
		Stack<String> s1 = new Stack<>();
		List<String> s2 = new ArrayList<>();
		
		for(String item : list) {
			
			if(item.matches("\\d+")) {
				//如果是数，入 s2 栈
				s2.add(item);
			}else if(item.equals("(")){
				//如果是 左括号，直接入 s1 栈
				s1.push(item);
			}else if(item.equals(")")){
				//如果是 右括号，要弹出 s1 中的运算符，直到碰到匹配的左括号，再去掉左括号
				while(!s1.peek().equals("(")) {
					//下一个不是 左括号 ，s1 中取出运算符放到 s2 中，这些运算符用于计算括号中的值
					s2.add(s1.pop());
				}
				//找到 ( 了，然后删掉
				s1.pop();
			}else {
				//如果运算符，分情况
				//returnOperLevel();用于计算运算符优先级
				
				//1.如果 s1为空，或栈顶运算符为左括号“(”，则直接将此运算符入s1栈；  
				//2.如果 若优先级比栈顶运算符的高，也将运算符压入 s1
				
				//3.如果，优先级小于等于栈顶运算符，将 s1栈顶的运算符弹出并压入到  s2中，
				//再次转到 (1.) 开头与 s1中新的栈顶运算符相比较；
				
				//这里判断第三种，因为前两种都是入栈
				while(s1.size() != 0 && returnOperLevel(item) <= returnOperLevel(s1.peek())) {
					//s1 中取运算符，入s2 栈，因为同级别，所以连续转栈，直到
					s2.add(s1.pop());
				}
				//将item入栈，符合剩余情况
				s1.push(item);
			}
		}
		
		//遍历完表达式，将s1 中运算符入 s2栈，得到结果
		while(s1.size()!=0) {
			s2.add(s1.pop());
		}
		
		//最后s2 是结果，本来是s2 栈逆序输出，但是用List就不用了
		return s2;
	}
	
	//计算运算符优先级，返回数字越大，越优先
	public static int returnOperLevel(String oper) {
		
		int res = -1;
		
		switch (oper) {
		case "+":
			res = 0;
			break;
		case "-":
			res = 0;
			break;
		case "*":
			res = 1;
			break;
		case "/":
			res = 1;
			break;
		default:
			break;
		}
		
		return res;
	}
}
